package algorithm.backtracking.leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * 回溯法解决电话号码转字母字符串问题
 * @author yuisama
 * @date 2021/12/25 19:51
 **/
public class Num17 {
    private String[] allLetters = {
            " ", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz" // 9
    };
    private List<String> ret = new LinkedList<>();
    public List<String> letterCombinations(String digits) {
        if (!digits.isEmpty()) {
            letterCombinationsInternal(digits,0,"");
        }
        return ret;
    }

    /**
     * 给定一个包含数组的字符串，返回能表示的字母组合
     * @param digits 所有的字符串
     * @param index 当前处理到digits的哪个字符
     * @param str 存储了digits[0..index - 1]翻译后的字母字符串
     */
    private void letterCombinationsInternal(String digits, int index,String str) {
        // 所有组合处理完毕，保存最后字符串
        if (index == digits.length()) {
            System.out.print(str + " ");
            ret.add(str);
            return;
        }
        // 当前处理的字符
        char c = digits.charAt(index);
        // 当前字符对应的字符串
        String letters = allLetters[c - '0'];
        for (int i = 0; i < letters.length(); i++) {
            // 将当前字符与子串拼接，然后index + 1继续向后处理
            letterCombinationsInternal(digits,index + 1,str + letters.charAt(i) );
        }
    }

    public static void main(String[] args) {
        new Num17().letterCombinations("23");
    }
}